//
//  DPSolution.cpp
//  leetcode
//
//  Created by Ellie on 2021/2/22.
//  Copyright © 2021 Ellie. All rights reserved.
//

#include <stdio.h>
#include "DPSolution.h"

int DPSolution::longestCommonSubsequence(string text1, string text2)
{
    int n = text1.size();
    int m = text2.size();
    
    dp2dtable = vector<vector<int>>(n, vector<int>(m, -1));
    return lcsrecursion(text1, n - 1 , text2,  m - 1);
}

//
// Recursion with DPTable Top to Bottom
// 直接使用Recursion会超时，需要dptable去除重复子问题
// 找出解决问题的暴力方法
// TOP to Bottom 实现方案 （递归拆分问题+DPTable减少重复子问题）
// 结果从下到上进行返回
// 通过递归可以看出来状态转换方程
//
int DPSolution::lcsrecursion(string& s1, int i, string& s2, int j)
{
    if(i < 0 || j < 0)
        return 0;
    if(dp2dtable[i][j] != -1)
        return dp2dtable[i][j];
    
    int value = 0;
    if(s1[i] == s2[j])
    {
        value = 1 + lcsrecursion(s1, i - 1, s2, j - 1);
    }
    else
    {
        int left = lcsrecursion(s1, i, s2, j - 1);
        int right = lcsrecursion(s1, i - 1, s2, j);
        value = max(left, right);
    }
    dp2dtable[i][j] = value;
    return value;
}

//
// Bottom to Top
// Dynamic Programing Bottom Up
// 状态转移方程递归的分支，画图解决问题
// 为什么是二维数组，因为递归方法中涉及到了上下两个方向
// dptable[n][m]从上到下，从左到右遍历解答
// 空字符行和列都是0
int DPSolution::longestCommonSubsequenceiterative(string text1, string text2)
{
    int n = text2.size();
    int m = text1.size();
    
    vector<vector<int>> dptable(n + 1, vector<int>(m + 1, 0));
    
    // each row
    for(int j=1;j<=n;j++)
    {
        for(int i=1;i<=m;i++)
        {
            char ch1 = text1[i-1];
            char ch2 = text2[j-1];
            if(ch1 == ch2)
                dptable[j][i] = dptable[j-1][i-1] + 1;
            else
                dptable[j][i] = max(dptable[j-1][i], dptable[j][i-1]);
        }
    }
    return dptable[n][m];
}


// Longest Increasing Sub-Sequence
// 明白DPtable的意义:当前元素的最长子序列携带的元素
// 这个递归方法不太容易画图想到base-base，画图
// 分析方法，填充到数组中

int DPSolution::lengthOfLIS(vector<int>& nums)
{
    int size = nums.size();
    vector<int> dptable(size, 1);
    
    for(int i=1;i<size;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(nums[i] > nums[j])
                dptable[i] = max(dptable[i], dptable[j] + 1);
        }
    }
    int result = 1;
    for(auto & value : dptable)
    {
        result = max(result, value);
    }
    return result;
}

int DPSolution::findNumberOfLIS(vector<int>& nums)
{
    int size = nums.size();
    if(size < 2)
        return size;
    vector<int> dptable(size, 1);
    vector<int> counttable(size, 1);
    int maxcount = 1;
    for(int i = 1;i<size;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(nums[i] > nums[j])
            {
                if(dptable[j] + 1 > dptable[i])
                    counttable[i] = counttable[j];
                else if(dptable[j] + 1 == dptable[i])
                    counttable[i] += counttable[j];
                dptable[i] = max(dptable[i], dptable[j] + 1);
            }
        }
        maxcount = max(maxcount, dptable[i]);
    }
    int result = 0;
    for(int i=0;i<size;i++)
    {
        if(maxcount == dptable[i])
            result += counttable[i];
    }
    return result;
}


int DPSolution::findLengthOfLCIS(vector<int>& nums)
{
    int result = 1;
    int count = 1;
    int size = nums.size();
    for(int i=1;i<size;i++)
    {
        if(nums[i] > nums[i -1])
            count ++;
        else
        {
            result = max(result, count);
            count = 1;
        }
    }
    return result;
}

// 5.最长回文子串
// 枚举所有可能的回文串
string DPSolution::longestPalindromeSimple(string s)
{
    int size = s.size();
    int startleft = 0;
    int len = 0;
    
    for(int i=0;i<size;i++)
    {
        expandpalindromicCheck(s, i, i, size, startleft, len);
        expandpalindromicCheck(s, i, i + 1, size, startleft, len);
    }
    return s.substr(startleft, len);
}

string DPSolution::longestPalindrome(string s)
{
    // 有最优子结构，最优子结构----》最优解
    // dptable[i][j] : [i，j]索引i到索引j，是否为回文字符串
    // 求解dptable[0][size - 1] 遍历方向为从下到上，从左边到右依次进行填充
    // 状态转换方程if(j - 1 == 1 && s[i]==s[j]) dptable[i][j] = true;
    // if(j - i > 1 && (dptable[i+1][j-1] && s[i] == s[j])) dptable[i][j] = true;
    
    int size = s.size();
    if(size < 2)
        return s;
    vector<vector<bool>> dptable = vector<vector<bool>>(size, vector<bool>(size, false));
    for(int i=0;i<size;i++)
    {
        dptable[i][i] = true;
    }
    
    int len = 0;
    int startleft = 1;
    for(int i=size-1;i>=0;i--)
    {
        for(int j = i + 1; j < size ;j ++)
        {
            if(s[i] == s[j])
            {
                if(j - i == 1 || dptable[i+ 1][j-1])
                {
                    dptable[i][j] = true;
                    if(dptable[i][j] && (j-i+1) > len)
                    {
                        startleft = i;
                        len = j - i + 1;
                    }
                }
            }
        }
    }
    return s.substr(startleft, len);
}

// 647. 回文子串 统计回文子串的个数
int DPSolution::countSubstringsSimple(string s)
{
    int size = s.size();
    if(size < 2)
        return size;
    int result = 0;
    
    // no need
    int left = 0;
    int len = 0;
    
    for(int i=0;i<size;i++)
    {
        result += expandpalindromicCheck(s, i, i, size, left, len);
        result += expandpalindromicCheck(s, i, i+1, size, left, len);
    }
    return result;
}

// 返回以i和j为中心进行扩散，所得到的回文字符串个数 result;
// left:最长回文起始坐标
// len:最长回文的长度
int DPSolution::expandpalindromicCheck(const string &s ,int i, int j, int size, int & left, int & len)
{
    int result = 0;
    int lefttemp = 0;
    int lentemp = 0;
    while(i >= 0 && j < size && s[i] == s[j])
    {
        result ++;
        lefttemp = i;
        lentemp = j - i + 1;
        i--;
        j++;
    }
    // 只更新最大回文字符的数据
    if(len < lentemp)
    {
        len = lentemp;
        left = lefttemp;
    }
    return result;
}

// 516. 最长回文子序列 难度一般比字串难度大
int DPSolution::longestPalindromeSubseq(string s)
{
    // 拆分子问题
    // dptable[i][j] : 表示以i为起点j为终点组成的字符串最长回文序列的长度
    // 求解dptable[0][n-1] : 二维表的右上角
    // 初始化： dptable[i][i]对称线都是1，table[0][0] = 1,table[1][1] = 1,.....，其余的都为0
    // 状态转移方程 dptable[i][j] 和 s[i],s[j]字符是否相等有关， if(s[i] == s[j]) dptable[i][j] = dptable[i+1][j-1] + 2;
    // if(s[i] != s[j]) dptable[i][j] = max(dptable[i][j-1],dptable[i+1][j]);
    int size = s.size();
    if(size < 2)
        return size;
    vector<vector<int>> dptable = vector<vector<int>>(size, vector<int>(size, 0));
    for(int i=0;i<size;i++)
    {
        dptable[i][i] = 1;
    }
    // 二维数组的遍历行从下往上，列从左到右，逼近我们的结果
    // 我们的结果是dptable[0][n-1],所有选择如下的遍历方法
    // 画表格找规律
    for(int i = size -1 ;i >=0 ;i--)
    {
        for(int j = i + 1;j<size;j++)
        {
            if(s[i] == s[j])
                dptable[i][j] = dptable[i + 1][j - 1] + 2;
            else
                dptable[i][j] = max(dptable[i+1][j], dptable[i][j-1]);
        }
    }
    return dptable[0][size - 1];
}

// 通过递归可以看出来状态转换方程
// 画图解决
int DPSolution::longestPalindromeSubseqRecursion(string s)
{
    int size = s.size();
    dp2dtable.clear();
    dp2dtable = vector<vector<int>>(size, vector<int>(size, -1));
    return longestPalindromeSubseqHelper(s, 0, size - 1, size);
}

// 通过递归可以看出来状态转换方程
// 画图解决问题
int DPSolution::longestPalindromeSubseqHelper(const string & s, int i, int j, int size)
{
    if(i > j)
        return 0;
    if(dp2dtable[i][j] != -1)
        return dp2dtable[i][j];
    int value = 0;
    if(i == j)
        value = 1;
    else if(s[i] == s[j])
        value = 2 + longestPalindromeSubseqHelper(s, i + 1, j - 1, size);
    else
    {
        int left = longestPalindromeSubseqHelper(s, i + 1, j , size);
        int right = longestPalindromeSubseqHelper(s, i, j - 1 , size);
        value = max(left, right);
    }
    dp2dtable[i][j] = value;
    return value;
}

// EASY
int DPSolution::maxSubArraySimple(vector<int>& nums)
{
    int size = nums.size();
    if(size == 0)
        return 0;
    int result = INT_MIN;
    int sum = 0;
    for(int i=0;i<size;i++)
    {
        sum += nums[i];
        if(sum < nums[i])
            sum = nums[i];
        result = max(sum, result);
    }
    return result;
}

int DPSolution::maxSubArray(vector<int>& nums)
{
    int size = nums.size();
    if(size == 0)
        return 0;
    vector<int> dptable = vector<int>(size, 0);
    dptable[0] = nums[0];
    int result = INT_MIN;
    for(int i=1;i<size;i++)
    {
        // 状态转移方程，发现dp[i]只和dp[i-1]有关，可以直接状态压缩
        dptable[i] = max(nums[i] + dptable[i-1], nums[i]);
    }
    // dptable 表示 每个下标的最有子结构
    for(int i=0;i<size;i++)
    {
        result = max(dptable[i], result);
    }
    return result;
}

int DPSolution::maxSubArrayMinimumMem(vector<int>& nums)
{
    int size = nums.size();
    if(size == 0)
        return 0;
    vector<int> dptable = vector<int>(nums[0], 0);
    int result = INT_MIN;
    for(int i=1;i<size;i++)
    {
        dptable[1] = max(nums[i] + dptable[0], nums[i]);
        dptable[0] = dptable[1];
        result = max(result, dptable[1]);
    }
    return result;
}

// 152. 乘积最大子数组
int DPSolution::maxProduct(vector<int>& nums)
{
    int size = nums.size();
    int maxproduct = 1;
    int minproduct = 1;
    
    int result = INT_MIN;
    for(int i=0;i<size;i++)
    {
        if(nums[i] < 0)
            swap(maxproduct, minproduct);
        maxproduct = max(nums[i], maxproduct);
        minproduct = min(nums[i], minproduct);
        result = max(result, maxproduct);
    }
    return result;
}
